package com.gaogzhen.datastructure.graph.directed;

import com.gaogzhen.datastructure.graph.undirected.Entry;
import com.gaogzhen.datastructure.stack.Stack;
import edu.princeton.cs.algs4.Digraph;

import java.util.Iterator;

/**
 * @author Administrator
 */
public class DepthFirstDirectedPaths {

    /**
     * 标记数据
     */
    private boolean[] marked;

    /**
     * 起点可达顶点到起点的路径
     */
    private int[] edgeTo;

    /**
     * 起点
     */
    private final int s;

    /**
     * 计算有向图G从给定起点s可达的路径
     *
     * @param G 有向图
     * @param s 起点
     * @throws IllegalArgumentException unless {@code 0 <= s < V}
     */
    public DepthFirstDirectedPaths(Digraph G, int s) {
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        this.s = s;
        validateVertex(s);
        dfs(G);
    }

    private void dfs(Digraph digraph) {
        Stack<Entry<Integer, Iterator<Integer>>> path = new Stack<>();
        // marked[v] = true;
        if (!marked[s]) {
            // 键值对起点-起点对应邻接表迭代器压入栈中
            marked[s] = true;
            Iterable<Integer> iterable = digraph.adj(s);
            Iterator<Integer> it;
            if (iterable != null && (it = iterable.iterator()) != null){
                path.push(new Entry<>(s, it));
            }
        }
        while (!path.isEmpty()) {
            Entry<Integer, Iterator<Integer>> entry = path.pop();
            int x;
            Iterator<Integer> it = entry.getValue();
            Integer f = entry.getKey();
            while (it.hasNext()) {
                // 当前顶点对应的邻接表迭代器还有元素，获取下一个元素
                x = it.next();
                if (!marked[x]) {
                    // 顶点未被标记，标记顶点且标记路径x->f
                    // f是x所在邻接表对应的顶点
                    marked[x] = true;
                    edgeTo[x] = f;
                    if (it.hasNext()) {
                        // 邻接表迭代器还有元素，重新压入栈
                        path.push(entry);
                    }
                    // 按照深度优先原则，把新标记顶点对应的键值对压入栈中，在下次循环时优先访问
                    Iterable<Integer> iterable = digraph.adj(x);
                    if (iterable != null && (it = iterable.iterator()) != null){
                        path.push(new Entry<>(x, it));
                    }
                    break;
                }
            }

        }
    }

    /**
     * 从起点s到给定的目的顶点v是否存在一条有向路径
     *
     * @param v 给定的顶点
     * @return {@code true} 存在一条从起点到顶点v的有向路径, {@code false} 不存在
     * @throws IllegalArgumentException unless {@code 0 <= v < V}
     */
    public boolean hasPathTo(int v) {
        validateVertex(v);
        return marked[v];
    }


    /**
     * 从起点到给定顶点路径集合
     *
     * @param v 给定顶点
     * @return 从起点到给定顶点路径集合
     * @throws IllegalArgumentException unless {@code 0 <= v < V}
     */
    public Iterable<Integer> pathTo(int v) {
        validateVertex(v);
        if (!hasPathTo(v)) {
            return null;
        }
        Stack<Integer> path = new Stack<Integer>();
        for (int x = v; x != s; x = edgeTo[x]) {
            path.push(x);
        }
        path.push(s);
        return path;
    }

    /**
     * 校验顶点索引v是否合理
     *
     * @param v 顶点v
     */
    private void validateVertex(int v) {
        int V = marked.length;
        if (v < 0 || v >= V) {
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V - 1));
        }
    }
}
